Java 并发编程-缓存一致性问题
为什么会导致缓存一致性问题
参考资料 Java并发编程：volatile关键字解析（写的超级棒啊！！！） 参考资料 Java内存模型详解（JMM）
计算机在执行程序时，每条指令都是在 CPU中执行的，而执行指令过程中，势必涉及到数据的读取和写入。由于程序运行过程中的临时数据是存放在主存（物理内存）当中的，这时就存在一个问题，由于 CPU执行速度很快，而从内存读取数据和向内存写入数据的过程跟 CPU执行指令的速度比起来要慢的多，因此如果任何时候对数据的操作都要通过和内存的交互来进行，会大大降低指令执行的速度。因此在CPU 里面就有了高速缓存。
也就是，当程序在运行过程中，会先将运算需要的数据从主存复制一份到 CPU 的高速缓存当中，CPU 操作这个数据时就可以直接在高速缓存里面进行，当运算结束之后，再将高速缓存中的数据刷新到主存当中。
举个简单的例子，比如下面的这段代码：
i = i + 1;
按照上面的思路，当线程执行这个语句时，会先从主存当中读取 i 的值，然后复制一份到高速缓存当中，然后 CPU 执行指令对 i 进行加 1 操作，然后将数据写入高速缓存，最后将高速缓存中 i 最新的值刷新到主存当中。
上面的这个操作在单线程下是没有问题的，但是在多线程中运行就会有问题了。在多核 CPU 中，每条线程可能运行于不同的 CPU 中，因此每个线程运行时有自己的高速缓存（对单核 CPU 来说，其实也会出现这种问题，只不过是以线程调度的形式来分别执行的）。
上面的那个代码，假设有两个线程同时执行，理想状态下是结果为 2，但是结果真的如此吗？
可能存在下面一种情况：初始时，两个线程分别读取 i 的值存入各自所在的 CPU 的高速缓存当中，然后线程A 进行加 1 操作，然后把 i 的最新值 1 写入到内存。此时线程B 的高速缓存当中 i 的值还是 0，进行加 1 操作之后，i 的值为 1，然后线程B 把 i 的值写入内存。
最终结果 i 的值是 1，而不是 2。这就是著名的缓存一致性问题。通常称这种被多个线程访问的变量为共享变量。
如何解决这种问题的？
1、在总线加 LOCK# 的方式（这种方式了解就好）
在早期的CPU当中，是通过在总线上加LOCK#锁的形式来解决缓存不一致的问题。
因为 CPU 和其他部件进行通信都是通过总线来进行的，如果对总线加锁的话，也就是说阻塞了其他 CPU 对其他部件访问（如内存），从而使得只能有一个 CPU 能使用这个变量的内存。
比如上面例子中 如果一个线程在执行 i = i +1，如果在执行这段代码的过程中，在总线上发出了 LOCK 的信号，那么只有等待这段代码完全执行完毕之后，其他 CPU才能从变量 i 所在的内存读取变量，然后进行相应的操作。这样就解决了缓存不一致的问题。
但是上面的方式会有一个问题，由于在锁住总线期间，其他 CPU无法访问内存，导致效率低下。所以就出现了缓存一致性协议。
补充知识：总线（Bus）是计算机各种功能部件之间传送信息的公共通信干线，它是由导线组成的传输线束。按照计算机所传输的信息种类，计算机的总线可以划分为数据总线、地址总线和控制总线，分别用来传输数据、数据地址和控制信号。总线是一种内部结构，它是cpu、内存、输入、输出设备传递信息的公用通道，主机的各个部件通过总线相连接，外部设备通过相应的接口电路再与总线相连接，从而形成了计算机硬件系统。关于如何发送 LOCK#信号的参考这里 聊聊CPU的LOCK指令
2、通过缓存一致性协议
最出名的就是 Intel 的 MESI 协议，MESI 协议保证了每个缓存中使用的共享变量的副本是一致的。
具体看下面的
缓存一致性协议（MESI）
参考资料 缓存一致性协议（MESI）详解 参考资料 CPU多级缓存
前面说了每个线程的变量都是存在它自己的工作内存中的，那如何保证这些共享变量改变之后能通知其它的线程这个共享变量已经改变了呢？
除了早期的在总线加 LOCK# 的方式，最出名的应该就是这个缓存一致性协议（MESI），MESI 协议保证了每个缓存中使用的共享变量的副本是一致的。
它核心的思想是：当 CPU 写数据时，如果发现操作的变量是共享变量，即在其他 CPU 中也存在该变量的副本，会发出信号通知其他 CPU 将该变量的缓存行置为无效状态，因此当其他 CPU 需要读取这个变量时，发现自己缓存中缓存该变量的缓存行是无效的，那么它就会从内存重新读取。
单核缓存中每个 Cache line 有两个标志位：dirty 和 valid 标志，它们很好的描述了 Cache 和 Memory之间的数据关系（数据是否有效，数据是否被修改），而在多核处理器中，多个核会共享一些数据，MESI 协议就包含了描述共享的状态。
在 MESI 协议中，每个 Cache line 有 4个状态，可用 2个 bit 表示
| 状态 | 描述 |
|---|---|
| Modified（修改） | 数据有效，数据被修改了，和内存中数据不一致，数据只存在于本 Cache 中。 |
| Exclusive（独享） | 数据有效，数据和内存中的数据一致，数据只存在于本 Cache 中。 |
| Shared（共享） | 数据有效，数据和内存中的数据一致，数据存在多个 Cache 中。 |
| Invalid（无效） | 数据无效，一旦数据被标记为无效，那效果就等同于它从来没被加载到缓存中。 |
缓存一致性协议工作流程/原理：
- CPU A 从缓存中读取了缓存行 a，其他 CPU 都没有读，这时这条缓存行的状态为 Exclusive（独享）状态。
- 这时 CPU B 也从缓存中读取了缓存行 a，这时这条缓存行的状态为 Shared（共享）状态。
- 当 CPU A 修改了缓存行 a，并从回写到缓存中，这时这条缓存行的状态为 Modified（修改）状态，然后会回写到主存中去。
- 每个 CPU 读取完缓存行之后都在内存中监听已读缓存行的状态，这时 CPU B 监听的缓存行 a 已被修改，此时，CPU B 就会把他设置为 Invalid（无效）状态，无效状态的数据会被丢弃，如果想继续操作的话，还需要到主存中重新获取。
- 最后，这条缓存行 a 在 CPU A 中的状态又会改为 Exclusive（独享）状态。
对于 Modified 和 Exclusive 状态而言总是精确的，他们在和该缓存行的真正状态是一致的，而 Shared 状态可能是非一致的。如果一个缓存将处于 Shared 状态的缓存行作废了，而另一个缓存实际上可能已经独享了该缓存行，但是该缓存却不会将该缓存行升迁为 Exclusive 状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的 copy 的数量，因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行。
MESI 状态转换图（这里的远程读取是指从主存读取数据）：
如果N个CPU同一时间要去修改同一份缓存行会怎样？
这里会有一个裁决机制，系统自动裁决。
什么是缓存行？
最小存储单元，根据CPU品牌不同，有可能是32字节、64字节或者128字节。
MESI 缓存的延迟问题
如下下图
MESI协议存在一个问题，就是当 CPU0 修改当前缓存的共享数据时，需要发送一个消息给其他缓存了相同数据的 CPU 核心，这个消息传递给其他 CPU 核心以及收到消息完成各自缓存状态的切换这个过程中，CPU 会等待所有缓存响应完成，这样会降低处理器的性能。为了解决这个问题，引入了 StoreBuffer 存储缓存。
处理器把需要写入到主内存中的值先写入到存储缓存 Store Buffer 中，然后继续去处理其他指令。当所有的 CPU 核心返回了失效确认时（当一个 CPU 核收到 Invalid 消息时，会把消息写入自身的 Invalidate Queue 中，随后异步将这个数据设为 Invalid 状态），数据才会被最终提交。但是这种优化又会带来另外的问题。
如果某个 CPU 尝试将其他 CPU 占有的共享数据写入到内存，消息提交给 Store Buffer 以后，当前 CPU 继续做其他事情，而如果后面的指令依赖于这个被写入内存的最新数据（由于 Store Buffer 还没有写入到内存），就会产生可见性问题（也就是值还没有更新到内存中，这个时候读取到的共享数据的值是错误的）。
所以 MESI 协议，可以保证缓存的一致性，但是无法保证实时性。
CPU 的三级缓存
参考资料 CPU多级缓存
这个是补充知识
一个高速缓存已经满足不了CPU的需求了（主要是加大一级缓存太贵了），开始衍变为多级缓存，像家用电脑这种基本都是二级缓存或者是三级缓存，在任务管理器中就可以看到（如下图所示，有三级缓存）
一级缓存速度最高，但储存的容量最小，以此类推。
下面是三级缓存的处理速度参考表
| 从CPU到 | 大约需要的CPU周期 | 大约需要的时间(单位ns) |
|---|---|---|
| 寄存器 | 1 cycle | |
| L1 Cache | ~3-4 cycles | ~0.5-1 ns |
| L2 Cache | ~10-20 cycles | ~3-7 ns |
| L3 Cache | ~40-45 cycles | ~15 ns |
| 跨槽传输 | ~20 ns | |
| 内存 | ~120-240 cycles | ~60-120ns |
有了多级缓存之后，程序的执行逻辑就是这样的：
当 CPU 要读取一个数据时，就像数据库缓存一样，获取数据时首先会在最快的缓存中找数据，如果缓存没有命中(Cache miss) 则往下一级找, 直到三级缓存都找不到时，那只有向内存要数据了。一次次地未命中，代表取数据消耗的时间越长。
缓存一致性和多线程同步的关系
参考资料 有了缓存一致性协议为什么还需要多线程同步？ - 柯南的回答
首先先明确：缓存一致性协议 和 多线程同步 分别作用的对象是什么？
从他们的名字就可以看出来，一个是作用于CPU（缓存），一个作用于线程。而一般来说软件层是无需管这个缓存一致性协议的，它是位于硬件层的东西，只是这个 缓存一致性协议 刚好有个小问题（MESI 缓存的延迟问题）可以用来顺带理解 volatile 关键字的作用，所以下面多写了个案例（场景一）
那么CPU（缓存）和线程之间又有什么关系呢？
他们之间的关系就是：多个 CPU 上同时跑的（并行），肯定是不同线程，但是不同的线程，可以跑在同一个 CPU 上（并发）。
也就是说，多线程同步与 CPU 核数无关，而 CPU（缓存）一致性，要解决的是 CPU 之间的同步问题，而不是线程之间的同步问题。
看如下三个应用场景理解它们的区别，其中场景一就是缓存一致性协议会遇到的问题（使用 volatile 关键字解决），场景二和三就是多线程同步需要解决的问题
场景一：可见性问题
需求：在一个 core 修改了一个变量，另一个 core 立马就能读到（需要使用 volatile）
上面已经说了多核处理时可能会存在缓存的延迟问题，所以有时可能不会马上更新缓存里的数据，这种时候就需要使用 volatile 关键字
volatile 利用 添加 内存屏障 + MESI 协议让 cache line 无效，从而实现可见性。
不过得明白，volatile 和 MESI 不是一个层面的东西，它们之间差了很多层封装。这里 volatile 能让 MESI 直接访问内存也是通过 JVM 翻译成机器指令执行的。
场景二：保证原子性
需求：保证代码执行的原子性
为了简化整个模型，先假设只有一颗 CPU core0 在运行，然后 A 和 B 线程同时在这个 core0 上运行。然后 A 和 B 线程同时执行
// x 初始化值为 0
x = x + 1
当 A 线程把 x 值（=0）从内存读到寄存器后，就被 CPU 给中断掉，并让出 CPU 给到线程 B。
然后线程 B 读取了 x=0，并进行了 x+1 计算，最后赋值给 x，写入内存 x（=1），随后 CPU 唤醒 A 线程。
线程 A 继续上一次的执行 x + 1 并赋值给 x，写入内存 x（=1）。
可以看到，在单 core 场景下，是没有缓存一致性问题的，但是依旧有多线程间的数据一致性问题，此时也就是多线程同步发挥的地方。而多线程同步，通过使用临界区（如同步代码块）、信号量和管程等方式，来避免这种因为 “错误” 中断而产生的不一致问题，具体到操作系统，就是屏蔽中断、锁方式等。
场景三：线程执行顺序
需求：例如修改了两个变量，要求另一个线程在读到这两个变量的时候，要按照相同的顺序，比如这样的代码：
如下
// core 1：
x = 1024; flag = true;
// core 2:
while (!flag) ; assert(x == 1024);
这段代码其实就假定了几件事情，对变量 x 的修改，要先于对 flag 的修改；并且在 core 2 中要感知到这样的顺序。
所以，所谓的「多线程同步」，大部分时候是需要保证这样的正确性，严谨一点地说，就是所谓的「顺序一致性」，「线性一致性」，而衡量一个程序的并发正确性（线程安全），往往也是基于这样的标准。
多线程同步，是取决于程序所定义的正确性，没有办法自动完成的，不论是 CPU 还是编译器，都没办法搞定。
MESI 和 volatile 的关系
volatile 和 MESI 这两个东西没有半点关系。MESI 是缓存一致性的一种实现手段，多核 CPU 为了保证缓存数据的一致性，通常有两种实现手段，一种是总线锁，另一种是缓存锁。
总线锁性能消耗大，缓存锁则一般通过缓存一致性来实现。因此 MESI 是 CPU 硬件级别的。
volatile 是 JAVA 的一种关键字，这个关键字只是告诉编译器这个变量是易变的，每次使用该变量时都要重新从内存读取，不要试图用寄存器保存它。
然后编译器产生的指令直接读取内存的时候，有可能命中缓存，这时候 MESI 确保不会脏读，如果编译器不产生直接读取内存的指令（没有使用 volatile），而是使用寄存器保存的数据，那么 MESI 可能会脏读，volatile 正是可以防止这一点.
关于更多 volatile 的细节看 volatile那篇笔记
内存一致性和缓存一致性的区别
参考资料 并发编程-内存一致性和缓存一致性的区别
两者所解决的问题不一样。一个是核心之间的缓存如何同步，一个是线程之间的内存如何同步。（同步：通信+可见）
- 缓存一致性（Cache Coherence），解决是多个缓存副本之间的数据的一致性问题。
- 内存一致性（Memory Consistency），保证的是多线程程序访问内存时可以读到什么值。
MESI：缓存一致性问题是由于多核处理器的每个核心都有属于自己的L寄存器和 WriteBuffer 引起的 CPU 缓存和内存间数据不一致问题。（L1缓存/WB/L2缓存/L3缓存）
内存屏障：内存一致性问题是由于多线程程序中，不同线程的工作内存对主内存访问的可见性问题引起的。（Read/Load/Use/Assign/Store/Write）
